public class Solution {
    //w:背包容量，N：物品数量，wt:物品对应重量，val:物品对应价值
    int knapsack(int N, int W, int[] wt, int[] val){
        //定义dp数组,dp[i][j] 表示从下标为[0-i]的物品⾥任意取，放进容量为j的背包，价值总和最⼤是多少
        int[][] dp= new int[N+1][W+1];
        //初始化数组
        for(int j=W;j>=wt[0];j--){
            dp[0][j]=dp[0][j-wt[0]]+val[0];
        }
        //递推
        for(int i=1;i<val.length;i++){//遍历物品
            for(int j=0;j<=W;j++){//遍历背包容量
                if(j<wt[i])dp[i][j]=dp[i-1][j];
                else dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-wt[i]]+val[i]);
            }
        }
        return dp[N-1][W];
    }
}
